/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree with
 * non-negative, distinct integer values
 * 
 */

public class RBTree {


	


  private RBNode nil;    //null node
  private RBNode dRoot;  //dummy root
  private int size;
	
  public RBTree(){
	  nil = new RBNode(-1);
	  nil.left = nil;
	  nil.right = nil;
	  nil.parent = nil;
	  dRoot = new RBNode(Double.POSITIVE_INFINITY);
	  dRoot.left = nil;
	  dRoot.right = nil;
	  dRoot.parent = nil;
	  size = 0;
  }
	
  
  /**
   * public boolean empty()
   * 
   * returns true if and only if the tree is empty
   *  
   */
  public boolean empty() {
    if (dRoot.left == nil) return true;
    return false;
  }
  
  

  /**
   * public boolean search(int i)
   * 
   * returns true if and only if the tree contains i
   *  
   */
  public boolean search(int i)
  {
	if (empty()) return false;
	return nodeSearch(dRoot.left, i);
  }
  
  public boolean nodeSearch(RBNode node, int i){
	  if (node.key() == i) return true;
	  if (node.key() < i){
		  if (node.right == nil) return false;
		  return nodeSearch(node.right, i);
	  }
	  if (node.key() > i){
		  if (node.left == nil) return false;
		  return nodeSearch(node.left, i);
	  }
	  return false;
  }

  /**
   * public void insert(int i)
   * 
   * inserts the integer i into the binary tree; the tree
   * must remain valid (keep its invariants).
   * the function returns the number of color flips, or 0 if i was already in the tree
   * 
   */
   public int insert(int i) {
	  if (empty()){
		  ++size;
		  dRoot.left = new RBNode(i, nil, nil, dRoot, "black");
		  return 0;
	  }
	  return 0;
   }
  
  /**
   * public void delete(int i)
   * 
   * deletes the integer i from the binary tree, if it is there;
   * the tree must remain valid (keep its invariants).
   * the function returns the number of color flips, or 0 if i was not in the tree
   * 
   */
   public int delete(int i)
   {
	   if(empty() || i != dRoot.left.key()) return 0;
	   dRoot.left = nil;
	   --size;
	   return 0;
   }
   
   /**
    * public int min()
    * 
    * Returns the smallest key in the tree, or -1 if the tree is empty
    * is empty, returns -1;
    * 
    */
   public int min()
   {
	   if (empty()) return -1;
	   return dRoot.left.key();
   }
   
   /**
    * public int max()
    * 
    * Returns the largest key in the tree, or -1 if the tree is empty
    */
   public int max()
   {
	   if (empty()) return -1;
	   return dRoot.left.key();
   }
   
  /**
   * public int[] toIntArray()
   * 
   * returns an int[] array containing the values stored in the tree,
   * in ascending order.
   * 
   */
  public int[] toIntArray()
  {
	 int[] arr = new int[size]; //
	 if (empty()) return arr;
	 arr[0] = dRoot.left.key();
	 return arr;
  }

   /**
    * public int size()
    * 
    * Returns the number of nodes in the tree.
    * 
    * precondition: none
    * postcondition: none
    */
   public int size()
   {
	   return size;
   }

  /**
   * public class RBNode
   * 
   * If you wish to implement classes other than RBTree
   * (for example RBNode), do it in this file, not in 
   * another file 
   *  
   */
  public class RBNode{
	  
	  int j = 0;
	  int i = 0;
	  public Double key;
	  public RBNode left;
	  public RBNode right;
	  public RBNode parent;
	  public String color;
	  public RBNode(int k, RBNode l, RBNode r, RBNode p, String c){
		  key = (double)k;
		  left = l;
		  right = r;
		  parent = p;
		  color = c;
	  }
	  
	  public RBNode(double k){
		  key = k;
		  color = "black";
	  }
	  
	  public int key(){
		  int k = (int) round(key);
		  return k;
	  }

}
  
  /**
 * @original author Shai Vardi
 * Modified for semester 2012/2013 a
 */

}